#include <iostream>

using namespace std;

/*
Do permution for the string, assume the string does not contain duplicate character.
for example:
Input: abcd
Output: abcd bacd cabd dabc
        abdc badc cadb dacb
		acbd bcad cbad dbac
		acdb bcda cbda dbca
		adbc bdac cdab dcab
		adcb bdca cdba dcba
*/

void swap( char &x, char &y)
{
	char temp = x;
	x = y;
	y = temp;
}

//
// this one is brief, but need to change original 
// str. Make sure original str is not read-only.
// 
// consider how to remove duplicate permutations 
// if there is duplicate character in the string.
//
void Permute1( char *str, int start, int length)
{
	if( start == length)
	{
		printf("%s\n",str);
		return;
	}

	for( int i= start; i<length; i++)
	{
		swap(str[start], str[i]);
		Permute1(str, start+1, length);
		swap(str[start], str[i]);
	}
	return;
}

void Permute2(char* str, char *out, bool* used, int start, int length )
{
	if( start == length)
	{
		out[length] = '\0';
		printf("%s\n",out);
		return;
	}

	for( int i=0; i<length; i++ )
	{
		if(used[i] == false)
		{
			out[start] = str[i];
			used[i] = true;
			Permute2(str, out, used, start+1, length);
			used[i] = false;
		}
	}
}

int main()
{
	char str[10] = "abcd";
	int len = strlen(str);

	Permute1(str, 0, len);
	cout<<"First permutation end\n"<<endl;

	bool *used = (bool*)malloc(len*sizeof(bool));
	if( !used) return -1;

	char *out = (char*)malloc((len+1)*sizeof(char));
	if(!out) return -1;

	memset(used, 0, len*sizeof(bool));
	memset(out, 0, len*sizeof(bool));

	Permute2( str, out, used, 0, len);

	free(used);
	free(out);
	cout<<"Press any key to terminate ..."<<endl;
	return getchar();
}